package Top200;

/**
 * @author zhangmin
 * @create 2022-02-21 11:20
 * base：dividend/1=dividend   dividend/-1=dividend>Int,min?-dividend:Int.max
 * 用减法代替除法，为提高效率，每次减去最小翻倍次数
 */
public class divide29 {
    public int divide(int dividend, int divisor) {
        if(dividend==0) return 0;
        if (divisor==1) return dividend;
        if (divisor==-1) {
            if (dividend>Integer.MIN_VALUE) return -dividend;
            else return Integer.MAX_VALUE;
        }

        long a=dividend,b=divisor;
        int sign=1;
        if ((a>0&&b<0) ||(a<0&&b>0)){
            sign=-1;
        }
        a=a>0?a:-a;
        b=b>0?b:-b;
        int res=div(a,b);
        if (sign>0) return res>Integer.MAX_VALUE?Integer.MAX_VALUE:res;
        return -res;
    }

    int div(long a,long b){
        if (a<b) return 0;
        long count=1;
        long tb=b;//用来迭代计算b的倍数
        while ((tb+tb)<=a){
            count+=count;
            tb+=tb;
        }
        return (int) (count+div(a-tb,b));
    }
}
